package com.majie.algorithm.tree;

import com.majie.algorithm.tree.printer.BinaryTreeInfo;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinarySearchTree<E extends Comparable<E>> implements BinaryTreeInfo {

    private Node<E> root;

    private int size;

    public int size( ) {
        return this.size;
    }

    public boolean isEmpty( ) {
        return this.size == 0;
    }

    public void clear( ) {
        this.root = null;
    }

    public boolean contains(E element) {
        return node(element) != null;

    }

    private Node<E> node(E element) {
        Node<E> node = this.root;
        while (node != null) {
            int cmp = compareTo(element, node.element);
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {
                return node;
            }
        }
        return null;
    }

    public void add(E element) {
        elementNotNullCheck(element);

        if (root == null) {
            root = new Node<>(element, null);
        } else {
            Node<E> node = root;
            Node<E> parent = null;
            int cmp = 0;
            while (node != null) {
                cmp = compareTo(element, node.element);
                parent = node;
                if (cmp > 0) {
                    node = node.right;
                } else if (cmp < 0) {
                    node = node.left;
                } else {
                    return;
                }
            }
            node = new Node<>(element, parent);
            if (cmp > 0) {
                parent.right = node;
            } else {
                parent.left = node;
            }
        }
        size++;
    }

    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }

    public void remove(E element) {
        Node<E> node = this.root;
        while (node != null) {
            int cmp = compareTo(element, node.element);
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {
                Node<E> parent = node.parent;
                if (parent.left != null) {
                    if (parent.left.element == element) {
                        parent.left = null;
                        return;
                    }
                }
                if (parent.right != null) {
                    if (parent.right.element == element) {
                        parent.right = null;
                        return;
                    }
                }
            }
        }
    }


    public int compareTo(E e1, E e2) {
        return e1.compareTo(e2);
    }

    /**
     * 层序遍历
     */
    public void levelTraversal( ) {
        if (root == null) {
            return;
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (queue.size() > 0) {
            Node<E> poll = queue.poll();
            System.out.println(poll.element);
            if (poll.left != null) {
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
        }
    }

    public Node<E> preNode( ) {
        if (root == null) {
            return null;
        }
        Node<E> eNode = root.left;
        if (eNode != null) {
            Node<E> right = eNode.right;
            Node<E> temp = eNode;
            while (right != null) {
                temp = right;
                right = right.right;
            }
            return temp;
        }
        return null;
    }


    /**
     * 判断是否为完全二叉树
     * 层序遍历
     * 1. 左边不为空,入队
     * 2. 左边为空,右边不为空,返回false
     * 3. 右边不为空,右边入队
     * 4. 右边为空,左边可能为空,也可能不为空,那么后面的结点都应该为叶子结点,否则返回false
     * 5. 遍历完返回true
     */
    public boolean isComplete( ) {
        if (root == null) {
            return false;
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        //是否是叶子结点
        boolean leaf = false;
        while (queue.size() > 0) {
            Node<E> node = queue.poll();
            // 5. 应该是叶子结点,但是不是叶子结点的话,返回false
            if (leaf && !node.isLeaf()) {
                return false;
            }
            // 1. 左边不为空
            if (node.left != null) {
                queue.offer(node.left);
            }
            // 2. 左边为空右边不为空的话
            else if (node.right != null) {
                return false;
            }
            // 3. 右边不为空,入队
            if (node.right != null) {
                queue.offer(node.right);
            }
            // 4. 右边为空,左边可能是空,也可能不空,那么剩下的结点多应该是叶子结点
            else {
                leaf = true;
            }
        }
        return true;
    }

    public int height2( ) {
        if (root == null) {
            return 0;
        }
        int height = 0;
        //存储着每一层的元素数量
        int levelSize = 1;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (queue.size() > 0) {
            Node<E> poll = queue.poll();
            levelSize--;
            if (poll.left != null) {
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
            //意味着即将访问下一层
            if (levelSize == 0) {
                height++;
                levelSize = queue.size();
            }
        }
        return height;
    }

    /**
     * 树的高度
     */
    public int height( ) {
        return height(root);
    }

    private int height(Node<E> node) {
        if (node == null) {
            return 0;
        }
        return Math.max(height(node.left), height(node.right)) + 1;
    }

    /**
     * 后续遍历
     */
    public void postorderTraversal( ) {
        postorderTraversal(root);
    }

    private void postorderTraversal(Node<E> node) {
        if (node == null) {
            return;
        }
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.println(node.element);
    }


    /**
     * 中序遍历
     */
    public void inorderTraversal( ) {
        inorderTraversal(root);
    }

    private void inorderTraversal(Node<E> node) {
        if (node == null) {
            return;
        }
        inorderTraversal(node.left);
        System.out.println(node.element);
        inorderTraversal(node.right);
    }

    /**
     * 前序遍历
     */
    public void preorderTraversal( ) {
        preorderTraversal(root);
    }

    private void preorderTraversal(Node<E> node) {
        if (node == null) {
            return;
        }
        System.out.println(node.element);
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }

    public void fontShow2(Node<E> node) {
        if (node == null) {
            return;
        }
        Stack<Node<E>> stack = new Stack<>();
        while (node != null) {
            stack.add(node);
            node = node.left;
        }
        while (!stack.isEmpty()) {
            Node<E> pop = stack.pop();
            System.out.println(pop.element);
            if (pop.right != null) {
                System.out.println(pop.right.element);
            }
        }
    }

    @Override
    public Object root( ) {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    @Override
    public Object string(Object node) {
        Node<E> myNode = (Node<E>) node;
        String parentString = "null";
        if (myNode.parent != null) {
            parentString = myNode.parent.element.toString();
        }
        return myNode.element + "_p(" + parentString + ")";
    }

    private static class Node<E> {
        private E element;

        private Node<E> left;

        private Node<E> right;

        private Node<E> parent;

        Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        /**
         * 是否是叶子结点
         */
        public boolean isLeaf( ) {
            return this.left == null && this.right == null;
        }
    }
}
